

#include "includes.h"

typedef YJK_OBJECT (*arith_func)(YJK_OBJECT, YJK_OBJECT);

#define BIGINT_BASE 1000000000

void
make_bigint(int32_t src, YJK_BIGINT *bi)
{
  bi->length = 2;
  bi->data[0] = (src % BIGINT_BASE);
  bi->data[1] = (src / BIGINT_BASE);
}


/** Ensures that all terms have the same sign.
 */
static void
bigint_normalize(YJK_BIGINT *bi)
{
  int i = bi->length - 1;
  while (bi->data[i] == 0) i--;
  if (bi->data[i] > 0) //positive bigint
    {
      i--;
      for(; i >=0; i--)
	{
	  if (bi->data[i] < 0)
	    {
	      bi->data[i + 1]--;
	      bi->data[i] += BIGINT_BASE;
	    }
	}
    }
  else //negative bigint
    {
      i--;
      for(; i >=0; i--)
	{
	  if (bi->data[i] > 0)
	    {
	      bi->data[i + 1]++;
	      bi->data[i] -= BIGINT_BASE;
	    }
	}
    }
}

/** Prints out a bigint after normalizing it.
 */
void
print_bigint(YJK_BIGINT *bi)
{
  bigint_normalize(bi);
  int32_t *c = bi->data + bi->length - 1;
  while (c > bi->data && *c == 0) c--;
  printf("%d", *c);
  if (*c > 0)
    {
      c--;
      while (c >= bi->data)
	{
	  printf("%09d", *c);
	  c--;
	}
    }
  else
    {
      c--;
      while (c >= bi->data)
	{
	  printf("%09d", abs(*c));
	  c--;
	}
    }
    printf("\n");
}


/** Find required size for bigint.  This is necessary after a multiplication operation, which can produce bigints of up to twice the size in memory as needed.
 */
void
clean_bigint(YJK_BIGINT *bi)
{
  int i = bi->length - 1;
  while (bi->data[i] == 0) i--; 
  if (i < 2) i = 2;
  bi->length = i + 1;
}



// returns overflow
int32_t
bigint_add_int32(YJK_BIGINT *bi, int32_t x, unsigned int place)
{
  int sign = 1; 
  if (x < 0) sign = -1;

  int32_t a = x % BIGINT_BASE;
  int32_t b = x / BIGINT_BASE;
  int32_t carry = 0;

  bi->data[place] += a;
  if (bi->data[place] <= -BIGINT_BASE)
    {
      carry = -1;
      bi->data[place] = bi->data[place] % BIGINT_BASE;
    }
  else if (bi->data[place] >= BIGINT_BASE)
    {
      carry = 1;
      bi->data[place] = bi->data[place] % BIGINT_BASE;
    }

  carry += b;
  int i = place + 1;
  while (carry && i < bi->length)
    {
      bi->data[i] += carry;
      carry = 0;
      if (bi->data[i] <= -BIGINT_BASE)
	{
	  carry = -1;
	  bi->data[i] = bi->data[i] % BIGINT_BASE;
	}
      else if (bi->data[i] >= BIGINT_BASE)
	{
	  carry = 1;
	  bi->data[i] = bi->data[i] % BIGINT_BASE;
	}
      i++;
    }

  return carry; //overflow
}


YJK_BIGINT *
bigint_mult(YJK_BIGINT *a, YJK_BIGINT *b, YJK_BIGINT *bi)
{
  unsigned int i, j;
  int64_t r;
  //clear destination bigint
  for (i = 0; i < bi->length; i++)
    {
      bi->data[i] = 0;
    }

  //do multiplication
  for (i = 0; i < b->length; i++)
    {
      for (j = 0; j < a->length; j++)
	{
	  r = (int64_t) a->data[j] * b->data[i];

	  bigint_add_int32(bi, r % BIGINT_BASE, i + j);

	  if (r > r % BIGINT_BASE) //overflow
	    {
	      bigint_add_int32(bi, r / BIGINT_BASE, i + j + 1);
	    }
	}
    }
  
  clean_bigint(bi); //remove extraneous length
  return bi;
}


static int
make_node(char *s, int sign)
{
  int32_t result = 0;
  unsigned int place = 1;
  char *t = s;

  //make 32 bit int
  while(*t >= '0' && *t <= '9' && t < s + 9)
    {
      result += (*t - '0') * place;
      place *= 10;
      t++;
    }

  if (result > BIGINT_BASE) return 0;

  return result * sign;
}


YJK_BIGINT *
yjk_parse_bigint(char *s)
{
  //find sign
  int sign = 1;
  if (*s == '-')
    {
      sign = -1;
      s++;
    }
  else if (*s == '+')
    {
      s++;
    }

  unsigned int len = strlen(s);
  unsigned int num_nodes = (len + 8) / 9;

  if(num_nodes < 2) num_nodes = 2;

  YJK_BIGINT *bi = malloc(sizeof(YJK_BIGINT) + num_nodes * sizeof(int32_t));
  make_bigint(0, bi);
  bi->length = num_nodes;

  char x[sizeof(YJK_BIGINT) + 8];
  YJK_BIGINT *multby = (YJK_BIGINT *) &x;
  make_bigint(BIGINT_BASE, multby);

  //convert to little endian order
  char *r = strdup(s);
  int i;
  //reverse order
  for (i = 0; i < len / 2; i++)
    {
      r[i] = s[len - i - 1];
      r[len - i - 1] = s[i];
    }

  //compute nodes
  i = 0;
  while(i < num_nodes && *r)
    {
      bi->data[i] = make_node(r, sign);
      r += 9;
      i++;
    }
  while(i < num_nodes)
    {
      bi->data[i] = 0;
      i++;
    }
  
  free(r);
  return bi;
}


//dest must have enough space for copy.
int
copy_bigint(YJK_BIGINT *bi, YJK_BIGINT *dest)
{
  dest->header.free = 0;
  dest->header.type = TYPE_BIGINT;
  dest->header.tag = bi->header.tag;
  dest->header.size = bi->header.size;
  dest->length = bi->length;
  int i;
  for (i = 0; i < bi->length; i++)
    {
      dest->data[i] = bi->data[i];
    }

  return 1;
}


/*** Addition ***/

YJK_OBJECT 
simple_add(YJK_OBJECT a, YJK_OBJECT b)
{
  int c = a.fixnum.value + b.fixnum.value;
  if (c > YJ_INTMAX || c < -YJ_INTMAX)
    {
      YJK_OBJECT bi = heap_alloc2(sizeof(YJK_BIGINT) + 8, TYPE_BIGINT, task_ptr);
      make_bigint(c, bi.bigint);
      bi.tagged.tag = TAG_PTR;
      return bi;
    }

  YJK_FIXNUM d;
  d.value = c;
  d.tag = 0;

  return (YJK_OBJECT) d;
}

YJK_OBJECT
add_fixnum_ratio(YJK_OBJECT a, YJK_OBJECT b)
{
  return (YJK_OBJECT) (void *) 0x0;
}

YJK_OBJECT
add_ratio_fixnum(YJK_OBJECT a, YJK_OBJECT b)
{
  return add_fixnum_ratio(b, a);
}


static YJK_OBJECT 
add_fixnum_complex(YJK_OBJECT a, YJK_OBJECT b)
{
  return (YJK_OBJECT) (void *) 0x0;
}


static YJK_OBJECT 
add_fixnum_float(YJK_OBJECT a, YJK_OBJECT b)
{

  YJK_OBJECT c = heap_alloc2(sizeof(YJK_FLOAT), TYPE_FLOAT, task_ptr);
  
  c.flt->value = a.fixnum.value + b.flt->value;
  c.tagged.tag = TAG_PTR;
  
  return c;
}


static YJK_OBJECT 
add_bigint(YJK_OBJECT a, YJK_OBJECT b)
{
  YJK_OBJECT c;

  //shorter bigint stored in b.
  if (b.bigint->length > a.bigint->length)
    {
      c.bigint = b.bigint;
      b.bigint = a.bigint;
      a.bigint = c.bigint;
    }

  unsigned int len = a.bigint->length + 1;
  
  c = heap_alloc2(BIGINT_SIZE(a.bigint) + sizeof(int32_t), 
		  TYPE_BIGINT, 
		  task_ptr);
  c.bigint->length = len;

  int i;
  //clear new bigint
  for (i = 0; i < c.bigint->length; i++)
    {
      c.bigint->data[i] = 0;
    }
  //add smaller bigint
  for (i = 0; i < b.bigint->length; i++)
    {
      int32_t overflow = bigint_add_int32(c.bigint, b.bigint->data[i], i);
      bigint_add_int32(c.bigint, overflow, i + 1);
    }
  for (i = 0; i < a.bigint->length; i++)
    {
      int32_t overflow = bigint_add_int32(c.bigint, a.bigint->data[i], i);
      bigint_add_int32(c.bigint, overflow, i + 1);
    }
  
  c.tagged.tag = TAG_PTR;
  return c;
}


YJK_OBJECT
add_fixnum_bigint(YJK_OBJECT a, YJK_OBJECT b)
{
  //convert fixnum, then add bignums
  char x[sizeof(YJK_BIGINT) + 8]; //stack allocate temporary bigint

  make_bigint(a.fixnum.value, (YJK_BIGINT *) x); 

  return add_bigint((YJK_OBJECT) (void *) &x, b);
}


YJK_OBJECT
add_bigint_fixnum(YJK_OBJECT a, YJK_OBJECT b)
{
  return add_fixnum_bigint(b, a);
}


static YJK_OBJECT
add_fixnum_complexi(YJK_OBJECT a, YJK_OBJECT b)
{
  return (YJK_OBJECT) (void *) 0x0;
}


YJK_OBJECT
make_ratio(YJK_OBJECT numerator, YJK_OBJECT denominator)
{
  YJK_OBJECT obj = heap_alloc2(sizeof(YJK_RATIO), TYPE_RATIO, task_ptr);

  obj.ratio->numerator = numerator;
  obj.ratio->denominator = denominator;

  obj.tagged.tag = TAG_PTR;
  return obj;
}


/*** Multiplication ***/

YJK_OBJECT
mult_fixnum(YJK_OBJECT a, YJK_OBJECT b)
{
  int64_t c = a.fixnum.value * b.fixnum.value;
  if (c > YJ_INTMAX || c < -YJ_INTMAX)
    {
      YJK_BIGINT *obj = (heap_alloc2(sizeof(YJK_BIGINT) + 12, TYPE_BIGINT, task_ptr)).bigint;
      obj->data[0] = (c % BIGINT_BASE);
      obj->data[1] = ((c / BIGINT_BASE) % BIGINT_BASE);
      obj->data[2] = (((c / BIGINT_BASE) / BIGINT_BASE) % BIGINT_BASE);
      return (YJK_OBJECT) obj;
    } 

  return (YJK_OBJECT) (void *) ((int32_t) (c & 0xffffffff));
}


YJK_OBJECT 
mult_fixnum_bigint(YJK_OBJECT a, YJK_OBJECT b)
{
  return (YJK_OBJECT) (void *) 0x0;
}

YJK_OBJECT 
mult_bigint_fixnum(YJK_OBJECT a, YJK_OBJECT b)
{
  return mult_fixnum_bigint(b, a);
}

YJK_OBJECT 
mult_fixnum_ratio(YJK_OBJECT a, YJK_OBJECT b)
{
  return (YJK_OBJECT) (void *) 0x0;
}

YJK_OBJECT
mult_bigint(YJK_OBJECT a, YJK_OBJECT b)
{
  return (YJK_OBJECT) (void *) 0x0;
}


//  FIXNUM,             BIGINT,             RATIO,             COMPLEX,             FLOAT,            COMPLEX_INEXACT
arith_func add_funcs[6][6] = {
  //FIXNUM
  {&simple_add,         &add_fixnum_bigint, &add_fixnum_ratio, &add_fixnum_complex, &add_fixnum_float },
  //BIGINT
  {&add_bigint_fixnum,  &add_bigint},
  //RATIO
  {&add_ratio_fixnum},
  //COMPLEX
  {&add_fixnum_complex},
  //FLOAT
  {&add_fixnum_float},
  //COMPLEX_INEXACT
  {&add_fixnum_complexi}
};

//  FIXNUM,              BIGINT,              RATIO,             COMPLEX, FLOAT, COMPLEX_INEXACT
arith_func mult_funcs[6][6] = {
  //FIXNUM
  {&mult_fixnum,         &mult_fixnum_bigint, &mult_fixnum_ratio},
  //BIGINT
  {&mult_bigint_fixnum,  &mult_bigint, },
  //RATIO
  { },
  //COMPLEX
  { },
  //FLOAT
  { },
  //COMPLEX_INEXACT
  { }
};


void *
add(void *a, void *b)
{
  int a_type = get_type(a);
  int b_type = get_type(b);

  arith_func f = add_funcs[a_type - TYPE_FIXNUM][b_type - TYPE_FIXNUM];
  if (!f)
    {
      printf("Add function not implemented for types %d and %d\n", a_type, b_type);
      exit(1);
    }

  YJK_OBJECT result = f((YJK_OBJECT) REMOVE_TAG(a), (YJK_OBJECT) REMOVE_TAG(b));
  return result.pointer;
}

